package com.example.algorithms.sort;

/**
 * @Author Zhang Jie
 * @Date 9/28/20
 * @Version 1.0
 */

import java.util.Arrays;

/**
 * 桶排序：
 * 核心思想是：将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。
 * 桶内排序完成之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
 * 一般的步骤：
 * 1. 先确定要排序的数据的范围；
 * 2. 然后根据范围将数据分到桶中（可以选择桶的数量固定，也可以选择桶的大小固定）；
 * 3. 之后对每个桶进行排序(可以用快速排序)；
 * 4. 之后将桶中的数据进行合并。
 *
 * 最好的时间复杂度为O(n)(n约等于桶的个数)，最坏的时间复杂度为O(nlogn)(所有的数都在一个桶里，就是快排的复杂度)
 * 平均时间复杂度为O(n)，大部分情况下分布比较均匀
 *
 * 非原地算法
 * 桶是否稳定要看放入桶中时是否是按顺序放置，桶内排序算法（快速排序）是否稳定
 *
 * 桶排序适合应用在外部排序中
 * （外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中）。
 *
 */
public class BucketSort {

    public static void sort(int[] arr, int bucketCount){
        if(arr==null||arr.length<2){
            return;
        }
        int len = arr.length;
        //确定数据的范围
        int min = arr[0];
        int max = arr[0];
        for(int i=0;i<len;i++){
            if(arr[i]<min){
                min=arr[i];
            }else if(arr[i]>max){
                max=arr[i];
            }
        }
        //确认每个桶表示的范围
        int valueRange = max-min+1;
        bucketCount = valueRange<bucketCount?valueRange:bucketCount;
        int bucketSize=valueRange/bucketCount;
        bucketCount = valueRange%bucketCount==0?bucketCount:(bucketCount+1);
        //将数据依次放入桶中
        int[][] buckets = new int[bucketCount][bucketSize];
        int[] bucketPosition=new int[bucketCount];//用于表明桶中的元素个数，满了之后进行扩展防止溢出
        for(int i=0;i<len;i++){
            int bucketIndex = (arr[i]-min)/bucketSize;
            if(bucketPosition[bucketIndex]==bucketSize){
                buckets[bucketIndex] = expandBucket(buckets[bucketIndex]);
            }
            buckets[bucketIndex][bucketPosition[bucketIndex]++]=arr[i];
        }
        //桶内排序
        for(int i=0;i<bucketCount;i++){
            buckets[i]=QuickSort.sortUp(buckets[i],bucketPosition[i]);
        }
        //桶内数据依次取出,其实可以和上面的循环合并一起
        int k=0;
        for(int i=0;i<bucketCount;i++){
            for(int j=0;j<bucketPosition[i];j++){
                arr[k++]=buckets[i][j];
            }
        }
        //打印
        System.out.println(Arrays.toString(arr));
    }

    private static int[] expandBucket(int[] arr){
        int size = arr.length;
        int[] arrNew = new int[size*2];
        System.arraycopy(arr,0,arrNew,0,size);
        return arrNew;
    }
}
